package com.shm.leetcode;

import java.util.*;

/**
 * @author: shm
 * @dateTime: 2020/10/12 10:20
 * @description: 530. 二叉搜索树的最小绝对差
 * 给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
 *
 *
 *
 * 示例：
 *
 * 输入：
 *
 *    1
 *     \
 *      3
 *     /
 *    2
 *
 * 输出：
 * 1
 *
 * 解释：
 * 最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
 *
 *
 * 提示：
 *
 * 树中至少有 2 个节点。
 * 本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同
 */
public class GetMinimumDifference {
    public int getMinimumDifference(TreeNode root) {
        int min = Integer.MAX_VALUE;
        List<Integer> list = new ArrayList<>();
        inOrderTree(root,list);
        for (int i = 1; i < list.size(); i++) {
            min = Math.min(min,list.get(i)-list.get(i-1));
        }
        return min;
    }

    public void inOrderTree(TreeNode root,List<Integer> list){
        if (root==null){
            return;
        }
        inOrderTree(root.left,list);
        list.add(root.val);
        inOrderTree(root.right,list);
    }

    public int getMinimumDifference_2(TreeNode root) {
        int min = Integer.MAX_VALUE;
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        while (!stack.isEmpty()||root!=null){
            while (root!=null){
                stack.push(root);
                root=root.left;
            }
            if (!stack.isEmpty()){
                root = stack.pop();
                list.add(root.val);
                root=root.right;
            }
        }
        for (int i = 1; i < list.size(); i++) {
            min = Math.min(min,list.get(i)-list.get(i-1));
        }
        return min;
    }

    int min;
    int pre;
    public int getMinimumDifference_3(TreeNode root) {
        min = Integer.MAX_VALUE;
        pre = -1;
        inOrderTree(root);
        return min;
    }

    public void inOrderTree(TreeNode root){
        if (root==null){
            return;
        }
        inOrderTree(root.left);
        if (pre==-1){
            pre = root.val;
        }else {
            min = Math.min(min,root.val-pre);
            pre = root.val;
        }
        inOrderTree(root.right);
    }

    public int getMinimumDifference_4(TreeNode root) {
        int min = Integer.MAX_VALUE;
        int pre = -1;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty()||root!=null){
            while (root!=null){
                stack.push(root);
                root=root.left;
            }
            if (!stack.isEmpty()){
                root = stack.pop();
                if (pre==-1){
                    pre=root.val;
                }else {
                    min = Math.min(min,root.val-pre);
                }
                root=root.right;
            }
        }
        return min;
    }
}
